// 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
//给定 n 是一个正整数。
// letcode  超时？？？？？ O(2^n)
console.time('test')

function climbStairs(n) {
    return n <= 2 ? n : climbStairs(n - 1) + climbStairs(n - 2)
}

let a = climbStairs(5)
console.timeEnd('test')
console.log(a)

console.time('test2')
//O(n)
function climbStairs2(n) {
    let arr = new Array(n)
    for(let i = 1; i <= n; i++) {
        if(i < 3) {
            arr[i - 1] = i
        } else {
            // 逐一递推得到结果
            arr[i - 1] = arr[i - 2] + arr[i - 3] 
        }
    }
    return  arr[n-1]
}

let b = climbStairs2(5)
console.timeEnd('test2')
console.log(b)